package test;

//第k小的数对距离：https://leetcode.cn/problems/find-k-th-smallest-pair-distance/

//时间复杂度：O(n*log(max)+n*log(n))
public class SmallestDistancePair {
	//本题这里为什么是<=而不是<?
	//=> 见补充
	//nums数组中，<=limit的数对有多少个
    public int f(int[] nums,int limit){
        int count=0;
        for(int l=0,r=0;l<nums.length;l++){
            while(r+1<nums.length&&nums[r+1]-nums[l]<=limit){
                r++;
            }
            count+=r-l;
        }
        return count;
    }
    public int smallestDistancePair(int[] nums, int k) {
        Arrays.sort(nums);
        int n=nums.length;
        //枚举所有可能的的第k小的数对距离limit
        //如果枚举值limit,<limit的距离==k-1，显然limit即为答案
        int max=nums[n-1]-nums[0];
        int l=0,r=max;
        int ret=0;
        while(l<=r){
            int mid=l+(r-l)/2;
            if(f(nums,mid)>=k){
                ret=mid;
                r=mid-1;
            }
            else{
                l=mid+1;
            }
        }
        return ret;
    }
}
